<html>
<head>
  <title>Tree</title>
  <basefont face="微软雅黑" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="Evernote Windows/307027 (zh-CN, DDL); Windows/6.1.0 (Win32);"/>
  <style>
    body, td {
      font-family: 微软雅黑;
      font-size: 10pt;
    }
  </style>
</head>
<body>
<a name="582"/>
<h1>Tree</h1>

<div>
<span><div><h2 style="text-align: center;"><span style="font-size: 32px; color: rgb(28, 51, 135); line-height: 46px;">Tree</span></h2></div><div><span style="line-height: 1.45;">目标</span><br/></div><div><ul><li><span style="line-height: 1.45;">·</span> <span style="line-height: 1.45;">理解树的数据结构及其使用方法；</span><br/></li><li><span style="line-height: 1.45;">·</span> <span style="line-height: 1.45;">树用于实现</span> <span style="line-height: 1.45;">ADT Map</span><span style="line-height: 1.45;">；</span><br/></li><li><span style="line-height: 1.45;">·</span> <span style="line-height: 1.45;">用列表来实现树；</span><br/></li><li><span style="line-height: 1.45;">·</span> <span style="line-height: 1.45;">用类和引用来实现树；</span><br/></li><li><span style="line-height: 1.45;">·</span> <span style="line-height: 1.45;">以递归数据结构实现树；</span><br/></li><li><span style="line-height: 1.45;">·</span> <span style="line-height: 1.45;">用堆来实现优先队列；</span><br/></li></ul></div><div><br/></div><div><span><span>    <span>    </span></span>树在计算机科学的各个领域中被广泛应用，包括操作系统，图形学，数据库系统和计算机网络。树结构和自然界的树有许多相似的地方，也有根、枝和叶，它们的不同之处在于计算机中的树结构根在顶部而叶子则在底部。</span></div><div><br/></div><div><span><font color="#AD0000" style="font-size: 16pt;"><b>树结构的几个性质：</b></font></span></div><div><ul><li><span>树是分层的</span></li><li><span>一个节点（</span><span>node</span><span>）的所有子节点（</span><span>children</span><span>）和另一个节点的子节点是完全独立的</span></li><li><span>每个叶节点（</span><span>leaf</span><span>）都是不同的</span></li><li><span>你可以将树下层的所有部分（叫做子树</span> <span>subtree</span><span>）移动到树的另一位置而不影响更下层的情况，这是由树的分层性决定的。例如，我们可以将所有标注</span><span>/etc</span><span>的子树从根节点下移动到</span><span>usr/</span><span>下面。这样做会将</span><span>httpd</span><span>的路径从</span><span>/etc/httpd</span><span>改变成</span><span>/usr/etc/httpd</span><span>，但是对</span><span>httpd</span><span>的内容及其子节点的内容不会有影响。</span></li></ul><div><img src="Tree_files/Image.png" type="image/png" data-filename="Image.png"/></div></div><div><table style="border-collapse: collapse; min-width: 100%;"><colgroup><col style="width: 215px;"></col><col style="width: 318px;"></col></colgroup><tbody><tr><td style="width: 215px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div>几个典型树结构的例子</div></td><td style="width: 318px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><br/></div></td></tr><tr><td style="width: 215px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span style="min-height: 12pt; font-size: 12pt;">生物学中的分类树</span></div></td><td style="width: 318px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><br/></div></td></tr><tr><td style="width: 215px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span style="min-height: 12pt; font-size: 12pt;">文件系统</span></div></td><td style="width: 318px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>在一个文件系统中，磁盘的分支或者文件夹构建成了一棵树</span></div></td></tr><tr><td style="width: 215px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>一个网页</span></div></td><td style="width: 318px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>树的每一层都对应 超文本标记符的一层嵌套。</span></div></td></tr></tbody></table><div><img src="Tree_files/Image [1].png" type="image/png" data-filename="Image.png" width="533"/></div></div><div><br/></div><div><div><br/></div><table style="border-collapse: collapse; min-width: 100%;"><colgroup><col style="width: 235px;"></col><col style="width: 334px;"></col></colgroup><tbody><tr><td style="width: 235px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div>术语名词</div></td><td style="width: 334px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><br/></div></td></tr><tr><td style="width: 235px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div>节点（Node）</div></td><td style="width: 334px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>基本构成部分</span></div><div><span>一个节点可能有更多的信息，我们称之为</span><span>“</span><span>负载（</span><span>payload</span><span>）</span><span>”</span></div><div><span><br/></span></div></td></tr><tr><td style="width: 235px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div>边（Edge）</div></td><td style="width: 334px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>边连接两个节点，并表示它们之间存在联系</span></div><div><span>入边：<span>节点（除了根节点）都有且只有一条</span></span></div><div><span>出边：<span>每个节点可能有许多条出边（从该节点指向其他节点的边）</span></span></div></td></tr><tr><td style="width: 235px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div>根节点（Root）</div></td><td style="width: 334px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>树中唯一一个没有入边的节点</span></div></td></tr><tr><td style="width: 235px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div>路径（Path）</div></td><td style="width: 334px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>由边连接起来的节点的有序排列</span></div><div><span>例如：动物界</span> <span>→</span> <span>脊索动物门</span> <span>→</span> <span>哺乳动物纲</span> <span>→</span> <span>食肉动物目</span> <span>→</span> <span>猫科</span> <span>→</span> <span>猫属</span> <span>→</span> <span>家猫 就是一条路径。</span></div></td></tr><tr><td style="width: 235px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div>子节点</div></td><td style="width: 334px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>当一个节点的入边来自另一个节点时，我们称前者是后者的子节点</span></div></td></tr><tr><td style="width: 235px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>子节点集（</span><span>Children</span><span>）</span></div></td><td style="width: 334px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>同一个节点的所有子节点构成子节点集</span></div></td></tr><tr><td style="width: 235px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>父节点（</span><span>Parent</span><span>）</span></div></td><td style="width: 334px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>一个节点是它的出边所连接的所有节点的父节点</span></div></td></tr><tr><td style="width: 235px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>兄弟节点（</span><span>Sibling</span><span>）</span></div></td><td style="width: 334px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>同一个节点的所有子节点互为兄弟节点</span></div></td></tr><tr><td style="width: 235px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>子树（</span><span>Subtree</span><span>）</span></div></td><td style="width: 334px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>子树是一个父节点的某个子节点的所有边和后代节点所构成的集合。</span></div></td></tr><tr><td style="width: 235px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>叶节点（</span><span>Leaf Node</span><span>）</span></div></td><td style="width: 334px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>没有子节点的节点成为称为叶节点</span></div></td></tr><tr><td style="width: 235px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>层数（</span><span>Level</span><span>）</span></div></td><td style="width: 334px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>一个节点的层数是指从根节点到该节点的路径中的边的数目</span></div></td></tr><tr><td style="width: 235px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>高度（</span><span>Height</span><span>）</span></div></td><td style="width: 334px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>树的高度等于所有节点的层数的最大值。</span></div></td></tr></tbody></table><div><br/></div></div><div><span>图</span><span>6.4</span><span>展示了一个符合定义一的树，每条边的箭头指出了连接的方向；</span></div><div><img src="Tree_files/Image [2].png" type="image/png" data-filename="Image.png" width="327"/></div><div><span>图</span><span>6. 4</span> <span>由节点和边构成的树</span></div><div><br/></div><div><br/></div><div><h2 style="text-align: center;"></h2><h2><br/></h2><h2 style="text-align: center;"></h2><h2><br/></h2><h2 style="text-align: center;"><span style="color: rgb(28, 51, 135); font-size: 24pt;">binary tree</span></h2><h2><span style="font-size: 16pt; color: rgb(28, 51, 135);">二叉树编程实现</span></h2><div style="box-sizing: border-box; padding: 8px; font-size: 12px; border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902);"><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">class TreeNode:</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    def __init__(self, val):</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        self.val = val</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        self.left, self.right = None, None</span></div><div><br/></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">#############################################################</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">&quot;&quot;&quot;遍历类的方法&quot;&quot;&quot;</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">#############################################################</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">class Traversal(object):</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    def __init__(self):</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        self.teaverse_path = list()</span></div><div><br/></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    def preorder(self, root):</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        if root:</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">            self.traverse_path.append(root.val)</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">            self.preorder(root.left)</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">            self.preorder(root.right)</span></div><div><br/></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    def inorder(self, root):</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        if root:</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">            self.inorder(root.left)</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">            self.traverse_path.append(root.val)</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">            self.inorder(root.right)</span></div><div><br/></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    def postorder(self, root):</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        if root:</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">            self.postorder(root.left)</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">            self.postorder(root.right)</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">            self.traverse_path.append(root.val)</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        </span></div></div><div><br/></div><h2><span style="font-size: 16pt; color: rgb(28, 51, 135);">Binary Search Tree - 二叉查找树</span></h2><div><span style="font-size: 12pt; color: rgb(173, 0, 0);">一颗</span><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">二叉查找树(BST)</span><span style="font-size: 12pt; color: rgb(173, 0, 0);">是一颗二叉树，其中每个节点都含有一个可进行比较的键及相应的值，且每个节点的键都</span><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">大于等于左子树中的任意节点的键</span><span style="font-size: 12pt; color: rgb(173, 0, 0);">，而</span><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">小于右子树中的任意节点的键</span><span style="font-size: 12pt; color: rgb(173, 0, 0);">。</span></div><div><br/></div><div><font color="#AD0000" style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">使用中序遍历可得到有序数组，这是二叉查找树的又一个重要特征。</span></font></div><div><br/></div><div><font color="#AD0000" style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">二叉查找树使用的每个节点含有两个链接，它是将链表插入的灵活性和有序数组查找的高效性结合起来的高效符号表实现。</span></font></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div></div><div><br/></div></span>
</div></body></html> 